We describe and analyse a simple greedy algorithm \2G\ that finds a good2-matching $M$ in the random graph $G=G_{n,cn}^{\d\geq 3}$ when $c\geq 15$. A2-matching is a spanning subgraph of maximum degree two and $G$ is drawnuniformly from graphs with vertex set $[n]$, $cn$ edges and minimum degree atleast three. By good we mean that $M$ has $O(\log n)$ components. We then usethis 2-matching to build a Hamilton cycle in $O(n^{1.5+o(1)})$ time \whp.
展开▼
机译：我们描述并分析一个简单的贪心算法\ 2G \，当$ c \ geq 15 $时，它会在随机图$ G = G_ {n，cn} ^ {\ d \ geq 3} $中找到匹配良好的$ M $。 A2匹配是最大度数为2的生成子图，而$ G $是从顶点集为[[n] $，边为$ cn $且最小度为至少三者的图中均匀绘制的。好的，我们的意思是$ M $具有$ O（\ log n）$分量。然后，我们使用2次匹配在$ O（n ^ {1.5 + o（1）}）$ time \ whp中建立汉密尔顿循环。
展开▼
